package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/10/4.
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 */
public class EntryNodeOfLoop {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 从上图中可以看出，环的入口结点和其他结点的区别：
     * 环的入口结点是有两个指针指向的，其他结点除了头结点都是只有一个指针指向的，
     * 使用断链法，在当前结点访问完毕后，断掉指向当前结点的指针。
     * 因此，最后一个被访问的结点一定是入口结点。
     * */
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode newHead = pHead;
        ListNode preNode = newHead;
        ListNode walkNode = newHead.next;
        if (preNode == null || preNode.next == null)
            return null;
        while (walkNode != null){
            preNode.next = null;
            preNode = walkNode;
            walkNode = walkNode.next;
        }
        return preNode;
    }
}
